package org.example.myleet.p1049;

public class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        //当neg = sum / 2时，能够使得sum - 2 * neg得到的剩余石头重量最小
        int neg = sum / 2;
        //表示对于前n块石头，能够配成0～neg重量的可能性
        boolean[][] dp = new boolean[stones.length + 1][neg + 1];
        dp[0][0] = true;
        for (int i = 0; i < stones.length; ++i) {
            int stone = stones[i];
            for (int j = 0; j <= neg; ++j) {
                if (j < stone) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    if (dp[i][j] || dp[i][j - stone]) {
                        dp[i + 1][j] = true;
                    }
                }
            }
        }
        int maxNeg = 0;
        for (int j = 0; j <= neg; ++j) {
            if (dp[stones.length][j]) {
                maxNeg = j;
            }
        }
        return sum - 2 * maxNeg;
    }
}
